package geek;

public class Tree_algorithm_day2 {
	
	public static <T extends Number> BSTNode<T> bstSearch(BSTNode<T> root, T val){
		BSTNode<T> ind = root;
		while(ind != null && ind.val != val){
			if(ind.val.doubleValue() > val.doubleValue()) ind = ind.left;
			else ind = ind.right;
		}
		return ind;
	}
	
	public static <T extends Number> BSTNode<T>[] bstSearchWithPar(BSTNode<T> root, T val){
		BSTNode<T> ind = root, par = null;
		while(ind != null && ind.val != val){
			if(ind.val.doubleValue() > val.doubleValue()){
				par = ind;
				ind = ind.left;
			}else{
				par = ind;
				ind = ind.right;
			}
		}
		
		BSTNode[] res = new BSTNode[2];//here BSTNode<T>[] res = BSTNode<T>[2]; is invalid
		res[0] = ind;
		res[1] = par;
		return res;
	}
	
	/**
	 * If the key is not equal to that of the root, 
	 * we search the left or right subtrees as before
	 * @param root : bst tree root
	 * @param val : value to be inserted
	 */
	public static <T extends Number> void bstInsert(BSTNode<T> root, T val){
		if(root == null) return;
		if(root.val.doubleValue() > val.doubleValue()){
			if(root.left == null) root.left = new BSTNode<T>(val);
			else bstInsert(root.left, val);
		}else if(root.val.doubleValue() < val.doubleValue()){
			if(root.right == null) root.right = new BSTNode<T>(val);
			else bstInsert(root.right, val);
		}
	}
	
	/**
	 * There are three possible cases to consider:
	 * 1) Deleting a leaf
	 * 		Delete this node
	 * 2) Deleting a node with one child
	 * 		Replace the node with its child
	 * 3) Deleting a node with two children
	 * 		Choose its in-order predecessor node or
	 * 		in-order successor node R,
	 * 		then exchange their value and delete R.
	 * 
	 * @param root
	 * @param val
	 */
	public static<T extends Number> BSTNode<T> bstDelete(BSTNode<T> root, T val){
		BSTNode<T>[] nodes = bstSearchWithPar(root, val);
		BSTNode<T> newroot = root;
		if(nodes[0].left == null && nodes[0].right == null) nodes[0] = null;//a leaf
		else if(nodes[0].left == null ^ nodes[0].right == null){//one child
			if(nodes[1] != null){
				BSTNode<T> child = nodes[0].left == null? nodes[0].left : nodes[0].right;
				if(nodes[1].left.equals(nodes[0])) nodes[1].left = child;
				else nodes[1].right = child;
			}else{//is the root
				if(nodes[0].left != null) newroot = nodes[0].left;
				else newroot = nodes[0].right;
			}
		}else{//two children
			//find successor
			//because it has two children, it always has the right child
			BSTNode<T> r = nodes[0].right;
			while(r.left != null) r = r.left;
			T temp = nodes[0].val;
			nodes[0].val = r.val;
			return bstDelete(root, temp);
		}
		nodes[0] = null;
		return newroot;
	}
	
	/**
	 * !If the node has right child, 
	 * the successor is its right child or the most left child of its right child
	 * If the node has no right child, and it's the left child of its parent
	 * the successor is its parent
	 * If the node has no right child, and it's the right child of its parent
	 * the successor is its first parents where the node is in it's left sub-tree
	 * 
	 * @param node
	 * @return
	 */
	public static <T extends Number> BSTNode<T> findInOrderSuccessor(BSTNode<T> node, BSTNode<T> root){
		BSTNode<T> res = null;
		if(node.right != null){
			res = node.right;
			while(res.left != null) res = res.left;
		}
		
		BSTNode<T> ind = null;
		while(ind != null){//just to a binary search
			if(node.val.doubleValue() < ind.val.doubleValue()){
				res = ind;
				ind = ind.left;
			}else if(node.val.doubleValue() > ind.val.doubleValue()){
				ind = ind.right;
			}else break;
		}
		return res;
	}
	
	/*public static <T extends Number> BSTNode<T> findInOrderPredecessor(BSTNode<T> node){
		
	}//*/
	
	

	
	public static void main(String[] args) {
		
	}

}

class BSTNode<T extends Number> implements Comparable<BSTNode>{
	public T val;
	public BSTNode<T> left = null;
	public BSTNode<T> right = null;
	
	public BSTNode(T val){
		this.val = val;
	}

	@Override
	public int compareTo(BSTNode o) {
		return (int) (this.val.doubleValue()-o.val.doubleValue());//ascending order
	}
}
